use std::{convert::TryInto, u32, usize};

fn main() {
    let n:u32 = 30;
    println!("use fib_1:");
    for i in 1..=n
    {
        print!("{} ", fib_1(i));
    }

    println!("\nuse fib_2:");
    for i in 1..=n
    {
        print!("{} ", fib_2(i));
    }

    println!("\nuse fib_3:");
    for i in 1..=n
    {
        print!("{} ", fib_3(i));
    }

    println!("\nuse fib_4:");
    for i in 1..=n
    {
        print!("{} ", fib_4(i));
    }
    println!("");
}

/// 递归实现.
///
fn fib_1(n: u32) -> u32 {
    if n == 1 || n == 2 {
        return 1;
    } else {
        return fib_1(n - 1) + fib_1(n - 2);
    }
}

/// 带备忘录的递归解法
///
fn fib_2(n:u32)->u32{
    if n < 1 {
        return 0;
    }
    let mut memo:Vec<u32> = vec![0; (1+n).try_into().unwrap()];

    return fib_2_helper(&mut memo, n);
}

fn fib_2_helper(memo:&mut Vec<u32>, n:u32)->u32{
    if n == 1 || n == 2{
        return 1;
    }
    if memo[n as usize] != 0{
        return memo[n as usize];
    }
    memo[n as usize] = fib_2_helper(memo, n-1) + fib_2_helper(memo, n-2);
    return  memo[n as usize];
}

/// dp 数组的迭代解法
///
fn fib_3(n:u32)->u32{
    if n == 1 || n == 2{
        return 1;
    }
    let mut dp:Vec<u32> = vec![0; (1+n).try_into().unwrap()];
    dp[1] = 1;
    dp[2] = 1;
    for i in 3..=n{
        dp[i as usize] = dp[(i-1) as usize ] + dp[(i-2) as usize];
    }
    return dp[n  as usize];
} 

/// 无备忘录、无dp 数组的迭代解法.
///
fn fib_4(n:u32)->u32{
    if n == 1 || n == 2{
        return 1;
    }
    let mut pre = 1;
    let mut curr = 1;
    
    for _i in 3..=n{
        let sum = pre + curr;
        pre = curr;
        curr = sum;
    }

    return  curr;
}